今天要來實作最後一個方法，也就是Heap Sort來解Sort an Array。
如果對Heap不熟悉或是已經淡忘的可以回頭先溫一下Day 24：一起來建構Min-Heap吧。
我們一樣會用到Parent和Child之間的關係，不過我們這次會採用Max-Heap的方式來實作！
Max Heap的特徵是第一個節點（node）具有最大值，且我們知道它是一個Unsorted的陣列。

如果要將資料由小到大排序，我們要做以下動作：

1. 把陣列中「第一個節點」和「最後一個節點」位置互換。
2. 假裝 heap的最後一個節點（陣列中的最後一個數）被移到我們存放結果的區域。
3. 再持續對第一個節點進行HeapifyDown()。並且把unsorted 的陣列長度-１，存放結果的區域長度+1

舉個例子來說，假設我們今天的input陣列為 array = [8, 5, 2, 9, 5, 6, 3]，
我們期望的 output = [2, 3, 5, 5, 6, 8, 9]。

我們可以很明顯的發現目前的input array是尚未排序的，
現在假裝有一個空陣列[ ]存放結果(result)，開始對input array以inplace的方式製造出Ｍax-heap，結果如下：

max-heap = [9, 8, 6, 5, 5, 2, 3]
result = []

所以現在我們知道最大的數會是9，於是我們直接把Ｍax-heap的頭尾做交換swap()

max-heap = [3, 8, 6, 5, 5, 2, 9]
不過我們想像現在的結果是長這樣
        => [3, 8, 6, 5, 5, 2][9]
前面的array是我們要繼續調整的部分，後面則是放結果的地方
我們再繼續把前面調整成 max-heap
max-heap = [8, 5, 6, 3, 5, 2]
重複上面的動作
        => [2, 5, 6, 3, 5][8]
而實際是    [2, 5, 6, 3, 5, 8, 9]

看完上面的動作不知道有沒有一點感覺了！
重複以上的方式我們會看到，後面已經排序的部分越來越長，這種排序方式可以達到時間複雜度不管是最糟還是平均都可以是Ｏ(nlogn)，因為我們建構Heap花了Ｏ(n)且加上約執行n回的Ｏ(logn)時間在做remove()的行為。而空間複雜度是Ｏ(1)。

最後來看實作吧！

function heapSort(array) {
  MaxHeapBuild(array);
  for (let endIdx = array.length - 1; endIdx > 0; endIdx--) {
    swap(0, endIdx, array);
    heapifyDown(0, endIdx - 1, array);
  }
  return array;
}

function MaxHeapBuild(array) {
  const firstParentIdx = Math.floor((array.length - 2) / 2);
  for (let currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
    heapifyDown(currentIdx, array.length - 1, array)
  }
}

function heapifyDown(currentIdx, endIdx, heap) {
  let leftChildIdx = currentIdx * 2 + 1;
  while (leftChildIdx <= endIdx) {
    const rightChildIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
    let swapIdx;
    if (rightChildIdx !== -1 && heap[rightChildIdx] > heap[leftChildIdx]) {
      swapIdx = rightChildIdx;
    } else {
      swapIdx = leftChildIdx;
    }
    if (heap[swapIdx] > heap[currentIdx]) {
      swap(currentIdx, swapIdx, heap);
      currentIdx = swapIdx;
      leftChildIdx = currentIdx * 2 + 1;
    } else {
      return;
    }
  }
}

function swap(i, j, heap) {
  const tmp = heap[j];
  heap[j] = heap[i];
  heap[i] = tmp;
}

明天是最後一天了 決定還是有始有終的再玩一題題目好了。

明日題目預告 : Find the closest element in Binary Search Tree